/**
 * 基数排序
 *
 * @Author: wanqian
 * @Date: 2021/2/3 10:08
 */
public class RadixSort {

//    public static int[] arr = {53, 3, 542, 748, 14, 214};

    public static void main(String[] args) {
        int[] arr = new int[1000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000);
        }
//        System.out.println(String.format("快速排序前： %s", Arrays.toString(arr)));
        long start = System.currentTimeMillis();
        radixSort(arr);
        long end = System.currentTimeMillis();
        long consume = (end - start);
        System.out.println("耗时" + consume + "毫秒");
//        System.out.println(String.format("快速排序后： %s", Arrays.toString(arr)));
    }

    public static void radixSort(int[] arr) {
        int count = 0;
        int[][] buckets = new int[10][arr.length];
        int[] bucketEle = new int[buckets.length];
        // 获得最大数
        // 根据最大数的位数判断需要排序几次
        int maxNum = arr[0];
        for (int ele : arr) {
            if (ele > maxNum) {
                maxNum = ele;
            }
        }
        int round = String.valueOf(maxNum).length();
        //排序round次
        for (int i = 0; i < round; i++) {
            for (int ele : arr) {
                //获得当前排序所需要比较的位数
                int compareNum = (ele / (int) Math.pow(10, i)) % 10;
                //放入对应的桶中
                buckets[compareNum][bucketEle[compareNum]++] = ele;
            }
            //按顺序从桶中取出放入原数组中
            int index = 0;
            //遍历所有桶
            for (int j = 0; j < buckets.length; j++) {
                //判断桶中是否包含元素
                if (bucketEle[j] > 0) {
                    //根据bucketEle中记录的对应桶中的元素数进行遍历
                    for (int k = 0; k < bucketEle[j]; k++) {
                        arr[index++] = buckets[j][k];
                    }
                    //因为桶中元素实际不会清空，会有上次排序的参与数据，所以不能使用增强for循环遍历所有元素
                    //通过bucketEle记录元素指针位置，来保证获取的都是有效数据
                    //当桶中数据全部取出后，通过重置0，相当于清空了桶
                    bucketEle[j] = 0;
                }
            }
//            System.out.println(String.format("第%d轮基数排序： %s", ++count, Arrays.toString(arr)));
        }
    }
}
